\chapter{Testovanie a analýza}

V tejto časti si predstavíme metodiku testovania, testovacie parametre, priebeh testovania, chyby a rovnako si predstavíme aj výsledky, ktoré zhodnotíme.

\section{Testovanie}

Testovanie prebiehalo na výpočetnom zväzku \textit{STAR} patriacej Fakulty informačních technologií.

Testovali sa spolu 4 rôzne inštancie, t.j. počítali sme dilatáciu pre grafy s počtom uzlov \textit{n = 11} s priemerným stupňom uzla postupne pre \textit{k = 4, k = 7 a k = 9} a pre \textit{n = 12, k = 7}. Pre každý taký graf sa pustila sekvenčná verzia programu, následne paralelná verzia postupne na 2, 4, 8, 16, 24 a 32 procesoroch. Paralelná verzia prebiehala jednak na rýchlej komunikačnej sieti \textit{InfiniBand} a jednak na sieti \textit{Ethernet}.

Do výstupných logov sme si zaznamenávali len informáciu o začatí výpočtu, dosiahntých konečných dilatácií a ukončení výpočtu. K tomu nechýbala informácia o tom, ako dlho výpočet prebiehal. 

V niekoľkých inštanciách sa stalo (približne 5-7), že program sa neukončil korektne, resp. posledný zostávajúci procesor v obehu nevyšiel pravdepodobne z hlavného cyklu. Tieto prípady nám ale zanechali všetky potrebné výsledky a ako celkový čas priebehu sa počítal ako čas behu posledného korektne dokončeného procesu.

\section{Výsledky testovania}

Pred testovaním sme mohli predpokladať, že časová zložitosť sa zlepší lineárne a to na základe toho, že všetky permutácie sme rovnomerne rozkladali medzi všetky procesory a dôležitá vlastnosť je, že sme potrebovali prejsť všetky permutácie. 

V tabuľke \ref{tab_ser} si predstavme časy sekvenčného behu programu. Podľa výsledných časov môžeme predpokladať, že čím má graf väčší priemerný stupeň uzla, tým výpočet trvá dlhšie. Všimnime si tiež, že pre graf s 12 vrcholmi sme neboli schopní získať výpočet pod hodinu. Avšak uvedieme ho, pretože v niektorých paralelných inštancií sme výpočet do hodiny získali a teda budeme môcť zistiť približný čas výpočtu za použitia sekvenčného programu.

\begin{table}[h!]
	\centering    
    \begin{tabular}{| l | l |} 
    \hline
    Inštancia & Čas (s) \\ \hline
    n = 11, k = 4 & 576 \\ \hline
    n = 11, k = 7 & 630 \\ \hline
    n = 11, k = 9 & 748 \\ \hline
    n = 12, k = 7 & $>$ 3600 \\
    \hline
    \end{tabular}
    \caption{Časy sekvenčného programu k jednotlivým grafom} 
    \label{tab_ser} 
\end{table}

V grafe \ref{fig:n11k4} vidíme časy prvej inštancie, kedy graf obsahoval 11 uzlov s priemerným stupňom uzla 4. Podľa grafu je zrejmé, že čím väčší počet procesorov, tým väčšie zrýchlenie. To znamená, že dosahujeme lineárne zrýchlenie. 

Podobne lineárne zrýchlenie pozorujeme aj pri ďalších inštanciách, čo vidno na grafoch \ref{fig:n11k7}, \ref{fig:n11k9} a \ref{fig:n12k7}.

\begin{figure}[h!]
	\centering
	\includegraphics[width=120mm]{../obr/n11k4.eps}
	\caption{Časy k počtu procesorov na jednotlivých sietiach pre n = 11, k = 4}
	\label{fig:n11k4} 
\end{figure}

\begin{figure}[h!]
	\centering
	\includegraphics[width=120mm]{../obr/n11k7.eps}
	\caption{Časy k počtu procesorov na jednotlivých sietiach pre n = 11, k = 7}
	\label{fig:n11k7}
\end{figure}

\begin{figure}[h!]
	\centering
	\includegraphics[width=120mm]{../obr/n11k9.eps}
	\caption{Časy k počtu procesorov na jednotlivých sietiach pre n = 11, k = 9}
	\label{fig:n11k9}
\end{figure}

Vďaka tomu, že sme počty procesorov na os X rozložili logaritmicky, tak vidíme, že zrýchlenie so stúpajúcim počtom procesorov nebude úplne lineárne. Je to dôsledok komunikačnej réžie medzi procesormi. 

Čo sa týka rozdielu medzi sieťou InfiniBand a Ethernetom, môžeme pozorovať, že nie je jednoznačné, ktorá sieť je rýchlejšia. Možno je to kvôli nenáročnej komunikácii, ktorá sa prejaví až pri výššom počte procesorov. To môžeme pozorovať na grafe \ref{fig:n12k7}, kde sieť InfiniBand je rýchlejšia. V tom prípade sa jedná o graf s 12 vrcholmi, kedy sme procesorom dali prechádzať oveľa väčšie množstvo permutácií ako v prípadoch s 11 vrcholmi. Totiž, v prípade s 11 vrcholmi a 32 procesormi, dostane na začiatku každý procesor približni 1 200 000 permutácií, ktoré má prejsť. No pri 12 vrcholoch a 32 procesoroch dostane na začiatku každý procesor takmer 15 miliónov permutácií, čo je desaťkrát viac. Keď porovnáme časy, tak 32 procesorov prešlo 1 200 000 permutácií za približne 20 sekúnd, ale rovnakých 32 procesorov dokázalo spracovať desaťkrát viac permutácií, za približne 300 sekúnd, no to je 15-krát viac. Z tohto faktu môžeme vyvodiť, že komunikačná réžia poružuje lineárny vzťah medzi veľkostou problému a počtom procesorov.

\begin{figure}[h!]
	\centering
	\includegraphics[width=120mm]{../obr/n12k7.eps}
	\caption{Časy k počtu procesorov na jednotlivých sietiach pre n = 12, k = 7}
	\label{fig:n12k7}
\end{figure}

